package DisjointSetUnion;

import java.util.HashMap;

public class MostStonesRemovedWithSameRowOrColumn {

    // 某一行第一个遇到的石头编号value
    public static HashMap<Integer, Integer> rowFirst = new HashMap<>();

    public static HashMap<Integer, Integer> colFirst = new HashMap<>();

    public static int max_n = 1001;
    public static int[] father = new int[max_n];

    public static int sets;

    public static void build(int n) {
        rowFirst.clear();
        colFirst.clear();
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        sets = n;
    }

    public static int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
            sets--;
        }
    }

    public static int removeStones(int[][] stones) {
        int n = stones.length;
        build(n);
        for (int i = 0; i < n; i++) {
            int row = stones[i][0];
            int col = stones[i][1];
            if (!rowFirst.containsKey(row)) {
                // 没有这一行的代表元素（root)
                rowFirst.put(row, i);
            } else {
                // 这一行上面的元素都被该行第一个石头代表
                union(i, rowFirst.get(row));
            }
            if (!colFirst.containsKey(col)) {
                // 没有这一列的代表元素（root)
                colFirst.put(col, i);
            } else {
                // 这一列上的元素都被该列第一个石头代表
                union(i, colFirst.get(col));
            }
        }
        // 最多能消除的石头数目 = 石头总数 - 剩下的石头
        return n - sets;
    }
}
